package day07_快速排序;

public class 快速排序1_version {

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void quickSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process1(arr, 0, arr.length - 1);
    }

    public static void process1(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        // L..R partition arr[R] [ <=arr[R] arr[R] >arr[R] ]
        int M = partition(arr, L, R);
        process1(arr, L, M - 1);
        process1(arr, M + 1, R);
    }

    // arr[L..R]上，以arr[R]位置的数做划分值
    // <= X > X
    // <= X X
    private static int partition(int[] arr, int L, int R) {
        int lessEqual = L - 1;
        int cur = L;
        while (cur <= R) {
            if (arr[cur] <= arr[R]) {
                swap(arr, cur++, ++lessEqual);
            }else {
                cur++;
            }
        }
        return lessEqual;
    }
}
